package 算法.leetcode.labuladong.数组和链表;

/**
 * @author lchenglong
 * @date 2022/6/16
 */
public class 在排序数组中查找第一个和最后一个位置 {
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            return new int[]{left_bound(nums,target),right_bound(nums,target)};
        }

        public int left_bound(int[] nums,int target) {
            int left = 0,right= nums.length-1;
            while (left<=right){
                int mid = left + (right-left)/2;
                if (nums[mid] == target){
                    // 往左侧边界靠拢
                    right = mid -1;
                } else if (nums[mid] > target) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            }
            if (left==nums.length||nums[left]!=target)return -1;
            return left;
        }

        public int right_bound(int[] nums,int target) {
            int left = 0,right= nums.length-1;
            while (left<=right){
                int mid = left + (right-left)/2;
                if (nums[mid] == target){
                    // 往右侧边界靠拢
                    left = mid +1;
                } else if (nums[mid] > target) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            }
            if (right<0||nums[right]!=target)return -1;
            return right;
        }
    }
}
